﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TopDownOperatorPrecedence
{
    public class PParser
    {
        public PNode AST { get; private set; }
        private Dictionary<string, PNode> symbolTable = new Dictionary<string, PNode>();

        private int tokenIndex;
        private PScope scope;
        private PNode currentNode;
        private List<PToken> tokens;

        private PNode MakeSymbol(string id, int bindingPower = 0)
        {
            if (symbolTable.ContainsKey(id))
            {
                PNode node = symbolTable[id];
                if (bindingPower > node.LeftBindingPower)
                {
                    node.LeftBindingPower = bindingPower;
                }
                return node;
            }
            else
            {
                PNode node = new PNode();
                node.ID = node.Value = id;
                node.LeftBindingPower = bindingPower;
                symbolTable[id] = node;
                return node;
            }
        }

        private PNode MakeInfix(string id, int bindingPower, Func<PNode, PNode, PNode> leftDenotation = null)
        {
            PNode node = MakeSymbol(id, bindingPower);
            if (leftDenotation == null)
            {
                leftDenotation = (curr, left) =>
                {
                    curr.First = left;
                    curr.Second = Expression(bindingPower);
                    curr.Arity = "binary";
                    return curr;
                };
            }

            node.LeftDenotationFunc = leftDenotation;
            return node;
        }

        private PNode MakeInfixr(string id, int bindingPower, Func<PNode, PNode, PNode> leftDenotation = null)
        {
            PNode node = MakeSymbol(id, bindingPower);
            if (leftDenotation == null)
            {
                leftDenotation = (curr, left) =>
                {
                    curr.First = left;
                    curr.Second = Expression(bindingPower - 1);
                    curr.Arity = "binary";
                    return curr;
                };
            }

            node.LeftDenotationFunc = leftDenotation;
            return node;
        }

        private PNode MakePrefix(string id, Func<PNode, PNode> nullDenotation = null)
        {
            PNode node = MakeSymbol(id);
            if (nullDenotation == null)
            {
                nullDenotation = curr =>
                {
                    this.scope.Reserve(curr);
                    curr.First = Expression(70);
                    curr.Arity = "unary";
                    return curr;
                };
            }

            node.NullDenotationFunc = nullDenotation;
            return node;
        }

        private PNode MakeAssignment(string id)
        {
            return MakeInfixr(id, 10, (curr, left) =>
            {
                if (left.ID != "." && left.ID != "[" && left.Arity != "name")
                {
                    throw new Exception("Bad left value");
                }

                curr.First = left;
                curr.Second = Expression(9);
                curr.IsAssignment = true;
                curr.Arity = "binary";
                return curr;
            });
        }

        private PNode MakeConstant(string id, string value, string type)
        {
            PNode node = MakeSymbol(id);
            node.NullDenotationFunc = curr =>
            {
                scope.Reserve(curr);
                curr.Value = symbolTable[curr.ID].Value;
                curr.ID = "(literal)";
                curr.Arity = "(literal)";
                curr.Type = type;
                return curr;
            };

            node.Value = value;
            return node;
        }

        private void InitializeSymbols()
        {
            MakeSymbol(":");
            MakeSymbol(";");
            MakeSymbol(",");
            MakeSymbol(")");
            MakeSymbol("]");
            MakeSymbol("}");
            MakeSymbol("else");
            MakeSymbol("in");

            MakeSymbol("(end)");
            MakeSymbol("(name)").NullDenotationFunc = curr => curr;

            MakeInfix("+", 50);
            MakeInfix("-", 50);
            MakeInfix("*", 60);
            MakeInfix("/", 60);
            MakeInfix("%", 60);

            MakeInfix("==", 40);
            MakeInfix("!=", 40);
            MakeInfix("<=", 40);
            MakeInfix(">=", 40);
            MakeInfix("<", 40);
            MakeInfix(">", 40);

            MakeInfix("?", 20, (curr, left) =>
            {
                curr.First = left;
                curr.Second = Expression(0);
                Advance(":");
                curr.Third = Expression(0);
                curr.Arity = "ternary";
                return curr;
            });

            MakeInfix(".", 80, (curr, left) =>
            {
                curr.First = left;
                if (currentNode.Arity != "name")
                {
                    throw new Exception("Expected a name token");
                }

                currentNode.Arity = "literal";
                curr.Second = currentNode;
                curr.Arity = "binary";
                Advance();
                return curr;
            });

            MakeInfix("[", 80, (curr, left) =>
            {
                curr.First = left;
                List<PNode> nodes = new List<PNode>();
                while (true)
                {
                    nodes.Add(Expression(0));
                    if (this.currentNode.ID != ":")
                    {
                        break;
                    }
                    this.Advance(":");
                }
                curr.Second = nodes.Count == 1 ? nodes[0] : new PNodeArray { Arity = "slice", ArrayObject = nodes, };
                curr.Arity = "binary";
                Advance("]");
                return curr;
            });

            MakeInfixr("&&", 30);
            MakeInfixr("||", 30);

            MakeAssignment("=");
            MakeAssignment("+=");
            MakeAssignment("-=");
            MakeAssignment("*=");
            MakeAssignment("/=");
            MakeAssignment("%=");

            MakePrefix("-");
            MakePrefix("+");
            MakePrefix("typeof");

            MakeConstant("true", "true", "bool");
            MakeConstant("false", "false", "bool");
            MakeConstant("null", "null", "object");

            MakeStat("{", curr =>
            {
                this.scope = new PScope(this.scope);
                PNode node = Statements();
                this.Advance("}");
                this.scope = this.scope.Parent;
                return node;
            });

            MakeStat("var", curr =>
            {
                List<PNode> stats = new List<PNode>();
                while (true)
                {
                    PNode node = currentNode;
                    if (node.Arity != "name")
                    {
                        throw new Exception("Expected a new variable name");
                    }

                    this.scope.Define(node);
                    this.Advance();
                    if (this.currentNode.ID == "=")
                    {
                        PNode tmp = this.currentNode;
                        this.Advance("=");
                        tmp.First = node;
                        tmp.Second = Expression(0);
                        tmp.Arity = "binary";
                        stats.Add(tmp);
                    }

                    if (this.currentNode.ID != ",")
                    {
                        break;
                    }
                    Advance(",");
                }
                Advance(";");
                return stats.Count == 0 ? null : (stats.Count == 1 ? stats[0] : new PNodeArray { ArrayObject = stats });
            });

            MakeStat("while", curr =>
            {
                this.Advance("(");
                curr.First = this.Expression(0);
                this.Advance(")");
                curr.Second = MakeBlock();
                curr.Arity = "statement";
                return curr;
            });

            MakeStat("for", curr =>
            {
                this.Advance("(");
                this.scope = new PScope(this.scope);
                List<PNode> stats = new List<PNode>();
                // Deal with empty statement
                if (this.currentNode.ID == ";")
                {
                    stats.Add(new PNode());
                    this.Advance(";");
                }
                else
                {
                    stats.Add(Statement());
                }

                if (this.currentNode.ID == ";")
                {
                    stats.Add(new PNode { ID = "(literal)", Value = "True", Type = "bool" });
                    this.Advance(";");
                }
                else
                {
                    stats.Add(Statement());
                }

                if (this.currentNode.ID == ")")
                {
                    stats.Add(new PNode());
                    this.Advance(")");
                }
                else
                {
                    stats.Add(Statement(")"));
                }

                curr.First = new PNodeArray { Arity = "for", ArrayObject = stats };
                this.Advance("{");
                curr.Second = Statements();
                this.Advance("}");
                curr.Arity = "statement";
                this.scope = this.scope.Parent;
                return curr;
            });

            MakeStat("foreach", curr =>
            {
                this.Advance("(");
                this.scope = new PScope(this.scope);
                if (this.currentNode.ID != "var")
                {
                    throw new Exception("Expect var keyword in foreach loop");
                }
                Advance("var");
                List<PNode> vars = new List<PNode>();
                while (true)
                {
                    PNode node = currentNode;
                    if (node.Arity != "name")
                    {
                        throw new Exception("Expect a variable name");
                    }

                    this.scope.Define(node);
                    vars.Add(node);
                    this.Advance();
                    if (this.currentNode.ID != ",")
                    {
                        break;
                    }
                    Advance(",");
                }

                Advance("in");
                PNode collection = Expression(0);
                curr.First = new PNode
                {
                    Arity = "foreach",
                    First = new PNodeArray { ArrayObject = vars },
                    Second = collection,
                };
                Advance(")");
                this.Advance("{");
                curr.Second = Statements();
                this.Advance("}");
                curr.Arity = "statement";
                this.scope = this.scope.Parent;
                return curr;
            });

            MakeStat("if", curr =>
            {
                this.Advance("(");
                curr.First = Expression(0);
                this.Advance(")");
                curr.Second = MakeBlock();
                if (this.currentNode.ID == "else")
                {
                    scope.Reserve(this.currentNode);
                    this.Advance("else");
                    curr.Third = this.currentNode.ID == "if" ? Statement() : MakeBlock();
                }
                else
                {
                    curr.Third = null;
                }

                curr.Arity = "statement";
                return curr;
            });

            MakeStat("break", curr =>
            {
                this.Advance(";");
                if (this.currentNode.ID != "}")
                {
                    throw new Exception("Unreachable statement.");
                }
                curr.Arity = "statement";
                return curr;
            });

            MakeStat("return", curr =>
            {
                if (this.currentNode.ID != ";")
                {
                    curr.First = Expression(0);
                }

                this.Advance(";");
                if (this.currentNode.ID != "}")
                {
                    throw new Exception("Unreachable statement.");
                }

                curr.Arity = "statement";
                return curr;
            });

            MakeStat("print", curr =>
            {
                if (this.currentNode.ID != ";")
                {
                    curr.First = Expression(0);
                }

                this.Advance(";");
                curr.Arity = "statement";
                return curr;
            });


            MakePrefix("(", curr =>
            {
                if (this.currentNode.ID == ")")
                {
                    Advance(")");
                    return new PNodeArray
                    {
                        ID = "parameters",
                        Arity = "parameters",
                        ArrayObject = new List<PNode>(),
                    };
                }
                PNode node = Expression(0);
                if (this.currentNode.ID != ",")
                {
                    // Normal Parenthesis
                    Advance(")");
                    return node;
                }
                else
                {
                    // Lambda expression header
                    List<PNode> elements = new List<PNode> { node };
                    PNodeArray header = new PNodeArray
                    {
                        ID = "parameters",
                        Arity = "parameters",
                        ArrayObject = elements,
                    };
                    while (true)
                    {
                        if (this.currentNode.ID != ",")
                        {
                            break;
                        }
                        Advance(",");
                        if (this.currentNode.Arity != "name")
                        {
                            throw new Exception("Expect a parameter name");
                        }
                        elements.Add(this.currentNode);
                        Advance();
                    }
                    Advance(")");
                    return header;
                }
            });

            MakeInfix("=>", 80, (curr, left) =>
            {
                if (left.Arity == "name" || left.Arity == "parameters")
                {
                    curr.Arity = "function";
                    curr.First = left;
                    if (this.currentNode.ID == "{")
                    {
                        this.Advance("{");
                        this.scope = new PScope(this.scope);
                        if (left.Arity == "name")
                        {
                            this.scope.Define(left);
                        }
                        else
                        {
                            PNodeArray parameters = left as PNodeArray;
                            foreach (var item in parameters.ArrayObject)
                            {
                                if (item.Arity != "name")
                                {
                                    throw new Exception("Expect parameter name in lambda para list");
                                }
                                this.scope.Define(item);
                            }
                        }
                        curr.Second = Statements();
                        this.scope = this.scope.Parent;
                        this.Advance("}");
                    }
                    else
                    {
                        this.scope = new PScope(this.scope);
                        curr.Second = Expression(0);
                        this.scope = this.scope.Parent;
                    }
                    return curr;
                }
                else
                {
                    throw new Exception("Invalid lambda expression");
                }
            });

            MakePrefix("function", curr =>
            {
                List<PNode> nodes = new List<PNode>();
                this.scope = new PScope(this.scope);
                if (this.currentNode.Arity == "name")
                {
                    this.scope.Define(this.currentNode);
                    curr.Name = this.currentNode.Value;
                    this.Advance();
                }

                this.Advance("(");
                if (this.currentNode.ID != ")")
                {
                    while (true)
                    {
                        if (this.currentNode.Arity != "name")
                        {
                            throw new Exception("Expect a parameter name");
                        }

                        this.scope.Define(this.currentNode);
                        nodes.Add(this.currentNode);
                        this.Advance();

                        if (this.currentNode.ID != ",")
                        {
                            break;
                        }
                        this.Advance(",");
                    }
                }

                curr.First = new PNodeArray { ArrayObject = nodes };
                this.Advance(")");
                this.Advance("{");
                curr.Second = Statements();
                this.Advance("}");
                curr.Arity = "function";
                this.scope = this.scope.Parent;
                return curr;
            });

            MakeInfix("(", 80, (curr, left) =>
            {
                List<PNode> nodes = new List<PNode>();
                if (left.ID == "." || left.ID == "[")
                {
                    curr.Arity = "ternary";
                    curr.First = left.First;
                    curr.Second = left.Second;
                    curr.Third = new PNodeArray { ArrayObject = nodes };
                }
                else
                {
                    curr.Arity = "binary";
                    curr.First = left;
                    curr.Second = new PNodeArray { ArrayObject = nodes };
                    if ((left.Arity != "unary" || left.ID != "function")
                        && left.Arity != "name" && left.ID != "("
                        && left.Arity != "&&" && left.ID != "||" && left.ID != "?")
                    {
                        throw new Exception("Expected a variable name");
                    }
                }

                if (this.currentNode.ID != ")")
                {
                    while (true)
                    {
                        nodes.Add(Expression(0));
                        if (currentNode.ID != ",")
                        {
                            break;
                        }
                        Advance(",");
                    }
                }
                Advance(")");
                return curr;
            });

            MakeSymbol("this").NullDenotationFunc = curr =>
            {
                scope.Reserve(curr);
                curr.Arity = "this";
                return curr;
            };

            MakeSymbol("(literal)").NullDenotationFunc = curr => curr;
            MakeSymbol("(literal)").NullDenotationFunc = curr => curr;

            MakePrefix("[", curr =>
            {
                List<PNode> nodes = new List<PNode>();
                if (this.currentNode.ID != "]")
                {
                    while (true)
                    {
                        nodes.Add(Expression(0));
                        if (this.currentNode.ID != ",")
                        {
                            break;
                        }
                        this.Advance(",");
                    }
                }
                this.Advance("]");
                curr.First = new PNodeArray { ArrayObject = nodes };
                curr.Arity = "unary";
                curr.Type = "list";
                return curr;
            });

            MakePrefix("{", curr =>
            {
                List<PNode> nodes = new List<PNode>();
                if (this.currentNode.ID != "}")
                {
                    while (true)
                    {
                        PNode node = this.currentNode;
                        if (node.Arity != "name" && node.Arity != "literal")
                        {
                            throw new Exception("Bad key");
                        }
                        this.Advance();
                        this.Advance(":");
                        PNode value = Expression(0);
                        value.Key = node.Value;
                        nodes.Add(value);
                        if (this.currentNode.ID != ",")
                        {
                            break;
                        }
                        Advance(",");
                    }
                }

                if (this.currentNode.ID == ",") // Remove possible trailing colon
                {
                    Advance(",");
                }
                Advance("}");
                curr.First = new PNodeArray { ArrayObject = nodes };
                curr.Arity = "unary";
                curr.Type = "object";
                return curr;
            });
        }

        private void Advance(string id = null)
        {
            if (id != null && this.currentNode.ID != id)
            {
                throw new Exception("Expected " + id);
            }

            if (this.tokenIndex >= tokens.Count)
            {
                this.currentNode = symbolTable["(end)"];
                return;
            }
            var token = this.tokens[this.tokenIndex];
            this.tokenIndex += 1;

            string value = token.Value;
            PTokenType type = token.Type;
            string typeText = null;
            PNode prototype = null;
            switch (type)
            {
                case PTokenType.Name:
                    prototype = scope.Find(value, symbolTable);
                    typeText = "name";
                    break;
                case PTokenType.String:
                case PTokenType.Number:
                    typeText = "literal";
                    prototype = symbolTable["(literal)"];
                    prototype.Type = type == PTokenType.Number ? "number" : "string";
                    break;
                case PTokenType.Operator:
                    if (symbolTable.ContainsKey(value))
                    {
                        prototype = symbolTable[value];
                        typeText = "operator";
                    }
                    else
                    {
                        throw new Exception("Unexpected operator " + value);
                    }
                    break;
                default:
                    throw new Exception("Unexpected token " + value);
            }

            this.currentNode = prototype.DeepClone();
            this.currentNode.Arity = typeText;
            this.currentNode.Value = value;
        }

        private PNode Expression(int rightBindingPower)
        {
            PNode left;
            PNode t = currentNode;
            Advance();
            left = t.NullDenotation();
            while (rightBindingPower < currentNode.LeftBindingPower)
            {
                t = this.currentNode;
                this.Advance();
                left = t.LeftDenotation(left);
            }
            return left;
        }

        private PNode Statement(string end = ";")
        {
            PNode node = currentNode;
            if (currentNode.StatementDenotationFunc != null)
            {
                this.Advance();
                this.scope.Reserve(node);
                return node.StatementDenotation();
            }

            PNode stat = Expression(0);
            //if (!stat.IsAssignment && stat.ID != "(")
            //{
            //    throw new Exception("Bad expression statement");
            //}

            this.Advance(end);
            return stat;
        }

        private PNode Statements()
        {
            List<PNode> nodes = new List<PNode>();
            PNode stat = null;
            while (true)
            {
                if (currentNode.ID == "}" || currentNode.ID == "(end)")
                {
                    break;
                }

                stat = this.Statement();
                if (stat != null)
                {
                    nodes.Add(stat);
                }
            }

            return nodes.Count == 0 ? null : (nodes.Count == 1 ? nodes[0] : new PNodeArray { ArrayObject = nodes });
        }

        private PNode MakeBlock()
        {
            PNode node = currentNode;
            Advance("{");
            return node.StatementDenotation();
        }

        private PNode MakeStat(string id, Func<PNode, PNode> statementDenotation)
        {
            PNode node = MakeSymbol(id);
            node.StatementDenotationFunc = statementDenotation;
            return node;
        }

        public PParser()
        {
            InitializeSymbols();
        }

        public PNode ParseStatements(List<PToken> tokens)
        {
            this.tokens = tokens;
            this.tokenIndex = 0;
            this.scope = new PScope(this.scope);
            Advance();
            PNode node = Statements();
            Advance("(end)");
            this.scope = this.scope.Parent;
            return node;
        }
    }
}
